/**
 * 
 */
package its.opt.graphs;

import its.opt.structures.NodeListItem;
import engine.individuals.Individual;

/**
 * @author test
 * 
 */
public class DecisionGraph<T extends Individual<Integer>> {

	private LabeledTreeNode root;

	private int numLeaves;
	private NodeListItem leaves;

	private LabeledTreeNode iterator;

	public DecisionGraph() {
		// create the root node

		root = new LabeledTreeNode(LabeledTreeNodeType.LEAF);

		// one leaf at the moment (the root)

		numLeaves = 1;

		// add the root to the list of leaf nodes

		leaves = new NodeListItem();
		leaves.nodeValue = root;
		leaves.previous = leaves.next = null;

		// add pointer to the root's item in the leaf list to the root

		root.leavesItem = leaves;

		// reset the iterators

		iteratorGoToRoot();
	}

	/**
	 * update the leaves (and other stuff) after performing a split
	 * 
	 * @param node
	 *          a pointer to the node the split was made on
	 * @return
	 */
	private int updateLeavesAfterSplit(LabeledTreeNode node) {
		NodeListItem item;
		NodeListItem newItem;

		// where is the leaf located in the list?

		item = node.leavesItem;

		// replace the original item for x by an item for its left child

		item.nodeValue = node.left;
		node.left.leavesItem = item;

		// create a new list item and insert it between item and item.next

		newItem = new NodeListItem();

		if (item.next != null) {
			item.next.previous = newItem; // redirect the right neighbour
		}

		newItem.next = item.next; // redirect the new item
		newItem.previous = item; // 
		item.next = newItem; // redirect the left neighbour

		// new item points to the right child

		newItem.nodeValue = node.right;
		node.right.leavesItem = newItem;

		// increase the number of leaves by 1 (we replaced one by two)

		/* private */numLeaves++;

		// x's got no items in the list anymore

		node.leavesItem = null;

		// get back

		return 0;
	}

	/**
	 * update the leaves (and other stuff) before performing a merge (we must do
	 * it before, because after doing it we will not have enough information to do
	 * this really)
	 * 
	 * @param x
	 * @param y
	 * @return
	 */
	private int updateLeavesBeforeMerge(LabeledTreeNode x, LabeledTreeNode y) {

		NodeListItem xItem, yItem;

		// assign x to the list item of the left child

		xItem = x.leavesItem;
		yItem = y.leavesItem;

		x.leavesItem = xItem;
		xItem.nodeValue = x;

		// delete the item for the right child

		if (yItem.previous != null) {
			yItem.previous.next = yItem.next;
		}

		if (yItem.next != null) {
			yItem.next.previous = yItem.previous;
		}

		if (yItem == leaves) {
			leaves = yItem.next;
		}

		// po co to?
		// Free(yItem);

		// decrement the number of leaves

		numLeaves--;

		// get back

		return 0;
	}

	/**
	 * deletes the list of nodes
	 * 
	 * @param x
	 *          the pointer to the first node in the node list to delete
	 * @return
	 */
	/*
	 * private int deleteNodeList(NodeListItem x) { if (x == null) return 0;
	 * 
	 * deleteNodeList(x.next); x = null;
	 * 
	 * return 0; }
	 */

	/**
	 * deletes the subtree from memory
	 * 
	 * @param x
	 *          the pointer to the root of the subtree (in fact, subgraph to
	 *          delete
	 * @return
	 */
	/*
	 * private int deleteSubtree(LabeledTreeNode x) {
	 *  // is the tree null?
	 * 
	 * if (x == null) return 0;
	 *  // delete the subtrees (careful about identical children)
	 * 
	 * if (x.left != x.right) { deleteSubtree(x.left); } deleteSubtree(x.right);
	 *  // cut the node from the parents (not to be deleted multiple times)
	 * 
	 * for (int i = 0; i < x.numParents; i++) { if (x.parent[i].left == x) {
	 * x.parent[i].left = null; } if (x.parent[i].right == x) { x.parent[i].right =
	 * null; } }
	 *  // if (x.parent != null) // free(x.parent); x.parent = null;
	 *  // delete the node itself
	 *  // delete x;
	 * 
	 * x = null;
	 *  // get back
	 * 
	 * return 0; }
	 */

	/**
	 * @return the iterator
	 */
	public LabeledTreeNode getIterator() {
		return iterator;
	}

	/**
	 * @return the leaves
	 */
	public NodeListItem getLeaves() {
		return leaves;
	}

	/**
	 * @return the numLeaves
	 */
	public int getNumLeaves() {
		return numLeaves;
	}

	/**
	 * @return the root
	 */
	public LabeledTreeNode getRoot() {
		return root;
	}

	public int iteratorFollowInstanceFromRoot(T x) {
		iterator = root;

		while (iterator.type != LabeledTreeNodeType.LEAF) {
			if (x.get(iterator.label) == 0) {
				iteratorGoLeft();
			} else {
				iteratorGoRight();
			}
		}

		return 0;
	}

	public int iteratorGoLeft() {
		// move the iterator to the left child, if possible

		iterator = iterator.left;

		// get back

		return 0;
	}

	public int iteratorGoRight() {
		// move the iterator to the right child, if possible

		iterator = iterator.right;

		// get back

		return 0;
	}

	public int iteratorGoTo(LabeledTreeNode x) {
		// move the iterator to the node x

		iterator = x;

		// get back

		return 0;
	}

	public int iteratorGoToRoot() {
		// move the iterator to the root

		iteratorGoTo(root);

		// get back

		return 0;
	}

	/**
	 * merges two leaves (not necessarily with the same parent)
	 * 
	 * @param x
	 * @param y
	 * @return
	 */
	public int merge(LabeledTreeNode x, LabeledTreeNode y) {
		
		int newParents;
		boolean found;

		// update the leaf list

		updateLeavesBeforeMerge(x, y);

		// redirect the y's parents to x instead of y

		for (int i = 0; i < y.numParents; i++) {
			if (y.parent[i].left == y) {
				y.parent[i].left = x;
			} else {
				y.parent[i].right = x;
			}
		}

		// assign all parents from y to x (only those that are new to x)

		newParents = 0;
		for (int i = 0; i < y.numParents; i++) {
			found = false;
			for (int j = 0; j < x.numParents; j++) {
				if (x.parent[j] == y.parent[i]) {
					found = true;
				}
			}

			if (!found) {
				newParents++;
			}
		}

		// resize parent
		LabeledTreeNode[] temp = x.parent;
		x.parent = new LabeledTreeNode[x.numParents + newParents];
		for (int i = 0; i < temp.length; ++i) {
			x.parent[i] = temp[i];
		}

		int k = x.numParents;
		for (int i = 0; i < y.numParents; i++) {
			found = false;
			for (int j = 0; j < x.numParents; j++) {
				if (x.parent[j] == y.parent[i]) {
					found = true;
				}
			}

			if (!found) {
				x.parent[k++] = y.parent[i];
			}
		}

		x.numParents += newParents;

		// printf("Mergin nodes x and y, adding %u new parents.\n",newParents);

		// get back

		return 0;
	}

	public double setValue(LabeledTreeNode x, double value, int which) {
		// set the value of a node and returns it

		return x.distribution[which] = value;
	}

	public int split(LabeledTreeNode node, int label) {
		// assign the label and type

		node.label = label;
		node.type = LabeledTreeNodeType.SPLIT;

		// split the node

		node.left = new LabeledTreeNode(LabeledTreeNodeType.LEAF);
		node.right = new LabeledTreeNode(LabeledTreeNodeType.LEAF);

		// allocate a parent for each of the children

		node.left.numParents = 1;
		node.left.parent = new LabeledTreeNode[1];

		node.right.numParents = 1;
		node.right.parent = new LabeledTreeNode[1];

		// assign the parent

		node.left.parent[0] = node.right.parent[0] = node;

		// assign the depths

		node.left.depth = node.right.depth = node.depth + 1;

		// replace the split node by its children

		/* private */updateLeavesAfterSplit(node);

		// get back

		return 0;
	}
}
